
public class MapImpl implements HashTable {
	private class Node{
		String key;
		String value;
		Node left = null;
		Node rigth = null;
		public Node(String key, String value){
			 this.key = key;
			 this.value = value;
		}
	}
	private int count;
	private Node root = null;
	
	public boolean isEmpty(){
		if (count == 0){
			return true;
		}
		else{
			return false;
		}
	}
	public int size(){
		return count;
	}
	public void put(String key, String value){
		if (root == null){
			root = new Node(key, value);
			count++;
		}
		else{
		 	Node current = root;
		 	Node parent = null;
		 	int comp = 0;
			while (current != null){
				parent = current;
				comp = current.key.compareTo(key);
				if (comp < 0){
					current = current.rigth;
				}
				else{
					if (comp > 0){
						current = current.left;
					}
					else{
						current.value = value;
						break;
					}
				}
			}
			if (comp < 0){
				parent.rigth = new Node(key, value);
				count++;
			}
			else{
				if (comp > 0){
					parent.left = new Node(key, value);
					count++;
				}
			}
		}
	}
	public String get(String key){
		Node current = root;
		while (current != null){
			int comp = current.key.compareTo(key);
			if (comp == 0){
				return current.value;
			}
			else if(comp < 0){
				current = current.rigth;
			}
			else{
				current = current.left;
			}
		}
		return null; // node with such a key doesn't exist in the tree;
	}
	public String remove(String key){
		final int STEP_LEFT = -1;
		final int STEP_RIGHT = 1;
		final int NO_STEP = 0;
		
		Node parent = null;
		Node current = root;
		int comp = 0;
		int lastStep = NO_STEP;
		while (current != null && (comp = current.key.compareTo(key))!= 0){
			parent = current;
			if (comp < 0){
				current = current.rigth;
				lastStep = STEP_RIGHT;
			}
			else{
				current = current.left;
				lastStep = STEP_LEFT;
			}
		}
		if (current == null){
			return null;
		}
		if (current.left == null){
			if (lastStep == STEP_RIGHT){
				parent.rigth = current.rigth;
				count--;
				return current.value;
			}
			else if (lastStep == STEP_LEFT){
				parent.left = current.rigth;
				count--;
				return current.value;
			}
			else{
				root = current.rigth;
				count--;
				return current.value;
			}
		}
		else if (current.rigth == null){
			if (lastStep == STEP_RIGHT){
				parent.rigth = current.left;
				count--;
				return current.value;
			}
			else if (lastStep == STEP_LEFT){
				parent.left = current.left;
				count--;
				return current.value;
			}
			else{
				root = current.left;
				count--;
				return current.value;
			}	
		}
		else{
			Node nodeToReplace = current.rigth;
			parent = current;
			String val = current.value;
			while (nodeToReplace.left != null){
				parent = nodeToReplace;
				nodeToReplace = nodeToReplace.left;
			}
			current.value = nodeToReplace.value;
			if(parent == current){
				parent.rigth = nodeToReplace.rigth;
			}
			else{
				parent.left = nodeToReplace.rigth;
			}
			count--;
			return val;
		}
	}
	public void clear(){
		root = null;
		count = 0;
	}
}
